/**
 * 面试题58-2：左旋转字符串
 */
public class Offer_58_II {
    /**
     * 方法三：书中写法（改用字符数组）
     * <p>
     * <ol>
     * <li>翻转前半部分</li>
     * <li>翻转后半部分</li>
     * <li>翻转整个，即得结果</li>
     * </ol>
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(n)
     */
    public String reverseLeftWords(String s, int n) {
        int len = s.length();
        char[] charArray = s.toCharArray();
        reverse(charArray, 0, n - 1);
        reverse(charArray, n, len - 1);
        reverse(charArray, 0, len - 1);
        return new String(charArray);
    }

    /**
     * 将 字符数组 指定区间内的字符翻转
     * 
     * @param charArray 字符数组
     * @param start     区间开始索引
     * @param end       区间结束索引（包含）
     */
    private void reverse(char[] charArray, int start, int end) {
        while (start < end) {
            char temp = charArray[start];
            charArray[start] = charArray[end];
            charArray[end] = temp;
            start++;
            end--;
        }
    }

    /**
     * 方法三：书中写法
     * <p>
     * <ol>
     * <li>翻转前半部分</li>
     * <li>翻转后半部分</li>
     * <li>翻转整个，即得结果</li>
     * </ol>
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(n)
     */
    public String reverseLeftWords3(String s, int n) {
        int len = s.length();
        StringBuilder builder = new StringBuilder(s);
        reverse(builder, 0, n - 1);
        reverse(builder, n, len - 1);
        reverse(builder, 0, len - 1);
        return builder.toString();
    }

    /**
     * 将 StringBuilder 指定区间内的字符翻转
     * 
     * @param builder 要翻转的 StringBuilder
     * @param start   区间开始索引
     * @param end     区间结束索引（包含）
     */
    private void reverse(StringBuilder builder, int start, int end) {
        while (start < end) {
            char ch = builder.charAt(start);
            builder.setCharAt(start, builder.charAt(end));
            builder.setCharAt(end, ch);
            start++;
            end--;
        }
    }

    /**
     * 方法二：遍历拼接
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(n)
     */
    public String reverseLeftWords2(String s, int n) {
        StringBuilder builder = new StringBuilder();
        for (int i = n; i < s.length(); i++) {
            builder.append(s.charAt(i));
        }
        for (int i = 0; i < n; i++) {
            builder.append(s.charAt(i));
        }
        return builder.toString();
    }

    /**
     * 方法一：substring 方法
     */
    public String reverseLeftWords1(String s, int n) {
        return s.substring(n, s.length()) + s.substring(0, n);
    }
}
